package com.algorithm.Tree;

public class BinaryTree<E> {
    protected Node<E> root;
    protected int size;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得元素的前驱
     */
    protected Node<E> precursor(Node<E> node) {
        if (node == null) return null;
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }

        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        return node.parent;
    }

    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;

        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        while (node.parent != null && node.parent.right == node) {
            node = node.right;
        }
        return node.parent;
    }

    protected void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must be not null");
        }
    }

    /**
     * visitor
     */
    public static abstract class Visitor<E>  {
        boolean stop;

        /**
         * 返回true就停止
         */
        abstract void visit(E element);
    }

    protected static class Node<E> {
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        E element;

        Node(E element,Node<E> parent) {
            this.parent = parent;
            this.element = element;
        }

        boolean hasTwoChild() {
            return left != null && right != null;
        }

        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        boolean isRightChild() {
            return parent != null && parent.right == this;
        }

        Node<E> sibling() {
            if (parent == null) return null;
            if (isLeftChild()) return parent.right;
            if (isRightChild()) return parent.left;
            return null;
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }
}
